package SwordForOffer.Problem40;

import java.util.HashMap;
import java.util.Map;

public class FindNumsAppearOnce {
	/*
	 * 一个整型数组里除了两个数字之外，其他的数字都出现了两次，找出这两个只出现了一次的数字
	 * 核心：利用异或的可抵消性，然后得到的数为1最高位，一位可以区分那两个只出现一次的数，同时相同的数会在同一组。
	 */
	public void findNumsAppearOnce(int[] array) {
		if(array==null)
			return ;

		int number=0;
		for(int i:array)
			// 异或
			number^=i;

		int index=findFirstBitIs1(number);
		int number1=0,number2=0;
		for(int i:array) {
			if(isBit1(i, index))
				number1^=i;
			else
				number2^=i;		
		}

		System.out.println(number1);
		System.out.println(number2);
		
	}
	private int findFirstBitIs1(int number) {
		int indexBit=0;
		while((number & 1)==0) {
			number=number >> 1;
			++indexBit;
		}
		return indexBit;
	}
	private boolean isBit1(int number,int index) {
		number=number >> index;
		return (number & 1)==0;
	}


	public void myFindNumsAppearOnce(int[] array) {
		Map<Integer,Integer> map = new HashMap<>();
		for (int num : array) {
			if (map.containsKey(num)){
				if (map.get(num) == 0){
					map.put(num,map.get(num) + 1);
				}else {
					map.put(num,map.get(num) - 1);
				}
			}else {
				map.put(num,1);
			}
		}
		for (int key : map.keySet()) {
			if (map.get(key) == 1){
				System.out.println(key);
			}
		}
	}
}
